The advent of computers, especially micro-computers, has led to a huge proliferation of communications systems, whether private or public. Private applications include the use of networks within a business or other single organization, and public ones include the provision of such things as automated teller machines by banks, as well as the provision of telephony.
In many cases the communications channels are susceptible to interlopers, who may have malicious or mischievous intent. Valuable information can be intercepted and data can be extracted without its legitimate users being aware of its loss.
It is often important to be able to protect sensitive information over large networks whether they are private or public. It is also important that the originators of information should be unable to deny that they sent it.
The prior art has seen rapid progress in the last twenty years. A first step towards providing widespread data security was the adoption in the United States of the Data Encryption Standard (DES), which was mandated as a published cipher by the National Bureau of Standards (see US Federal Register, Mar. 17, 1975, Volume 40, No. 52, and Aug. 1, 1975, Volume 40, No. 149). Use of the DES in such things as banking transactions is regarded as the due exercise of care under US law.
DES is a conventional cipher, inasmuch as the encrypting key must be the same as the decrypting key. The security of DES depends on the key being kept secure, so that if two parties wish to communicate they must arrange a safe way of establishing their common key. This is usually done by means of a courier who must physically travel between two points.
These problems of cost and time join those that arise if two parties wishing to communicate privately have had no previous contact, or when one party wishes to communicate with a lot of others at the same time.
Another problem with a cipher such as the DES is that receivers can send themselves messages which appear to come from a genuine sender. This is possible because of the key duplication (See M. E. Hellman, "The mathematics of public-key cryptography" Scientific American, Volume 241, No. 2, August 1979, pp 130-139.)
In 1977 Diffie and Hellman put forward the idea of a public key system (PKS) for cryptographic communications. In this type of cipher, the keys are not the same at each end of a communications link. In fact, half of the key can be published, in either a telephone book, or newspaper. (See "New directions in cryptography", IEEE Transactions on Information Theory, Volume IT-22, No. 6, November 1976, pp 109-112.)
Anyone wishing to communicate with someone who used a PKS would be able to obtain their public key, encrypt their message with it, and only the intended recipient would be able to decrypt it by using their secret key. This secret key is the other half of the public key. A sender can use their private key to sign a message, as, when decrypted with their known public key half, the message could only have originated with the holder of the private key. Hence the sender is unable to deny sending the signed message.
Within a year, Rivest, Shamir, and Adleman published the first practical PKS, known for the inventors as the RSA. (See R. Rivest, A. Shamir, L. Adleman, "A method for obtaining digital signatures and public key cryptosystems", Commun. ACM, 21 (1978) 120-126.)
The inventors gained a United States patent for their method (U.S. Pat. No. 4,405,829 granted Sep. 20, 1983) and the RSA cipher has been successfully implemented throughout the world.
The success of this cipher has led to increasing research into its cryptographic strength. These have largely led to strengthenings of the RSA, as attacks on the cipher have usually been easily countered.
The RSA is based on an exponential or "first order" linear recurrence, and could be vulnerable because of its multiplicative nature. The signature of a product is the product of the signatures. If M is one message, and N another sent by the same sender using the same key, with d being the exponent (or secret key) , then this multiplicative nature can be illustrated like this: EQU M.sup.d .multidot.N.sup.d =(M.multidot.N).sup.d
R. L. Rivest, writing as co-author of a 1988 paper, states that "The RSA scheme is selectively forgeable using a directed chosen-message attack, since RSA is multiplicative . . . " A selective forgery is a forged signature for a particular message chosen beforehand by the interloper. Although interlopers may be unable to decode messages, they may be able to recombine or reuse individual messages for which they have learned both the original message and the cipher, including the signatures of other people. Thus with reference to the example above, an interloper who knows both original messages M and N, and their cryptograms, can create and correctly encode a third message M.multidot.N without requiring knowledge of the key d. As the paper states, this aspect of the RSA can be protected against by padding out the message space with a "reasonably long checksum" among other ways. (See S. Goldwasser, S. Micali, R. L. Rivest, "A secure digital signature scheme" SIAM J. Comput., Volume 17, No. 2, April 1988, pp 281-308.)
This usually means that signed message must have other extraneous characters added in to protect RSA signatures against selective forgery.